package com.zlk.algorithm.huawei.leetcode.list;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName Code15_getIntersectionNode
 * @description:
 * @author: slfang
 * @create: 2025-01-07 11:02
 * @Version 1.0
 **/
public class Code15_getIntersectionNode {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;              //         |
        }
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int n1 = 0;
        int n2 = 0;
        // 一定会要用cur1.next 不然遍历到最后是null，而不是最后一个节点
        // cur1最后也会是null
        while (cur1.next!=null){
            n1++;
            cur1 = cur1.next;
        }
        while (cur2.next!=null){
            n2++;
            cur2 = cur2.next;
        }
        if(cur1!=cur2){
            return null;
        }
//        cur1 = n1>=n2?headA:headB;
//        cur2 = n2<n1?headB:headA;
//        int diff =Math.abs(n1-n2);
        if (n1-n2 >= 0) {
            cur1 = headA;
            cur2 = headB;
        } else {
            cur1 = headB;
            cur2 = headA;
        }
        int n =Math.abs(n1-n2);
        n = Math.abs(n);
        while (n!=0){
            cur1=cur1.next;
            n--;
        }
        while (cur1!=cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }


    @Test
    public void test(){
        ListNode headA = new ListNode(4);
        ListNode headB = new ListNode(5);
        headB.next = new ListNode(6);

        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(8);
        ListNode head3 = new ListNode(4);
        ListNode head4 = new ListNode(5);


        headA.next = head1;
        headA.next.next = head2;
        headA.next.next.next = head3;
        headA.next.next.next.next = head4;


        headB.next.next = head1;
        headB.next.next.next = head2;
        headB.next.next.next.next = head3;
        headB.next.next.next.next.next = head4;
        getIntersectionNode(headA,headB);
    }

    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}

